home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / smaltalk / st80_vw.lha / st80_vw / hashStatistics.st < prev    next >
Text File  |  1993-07-24  |  4KB  |  110 lines
  1. "       NAME            hashStatistics.st
  2.         AUTHOR          bruce@utafll.uta.edu (Bruce Samuelson)
  3.         FUNCTION        measures hash efficiency of Set, Dict, subclasses
  4.         ST-VERSIONS     ParcPlace VisualWorks 1.0 and ObjectWorks 4.1
  5.         PREREQUISITES   none
  6.         CONFLICTS       none
  7.         DISTRIBUTION    world
  8.         VERSION         1.0
  9.         DATE            July 8, 1993
  10.  
  11. SUMMARY These methods in the 'public domain' protocols of Set and Bag measure
  12. how well a Set, Dictionary, IdentitySet, or IdentityDictionary is hashed.
  13.  
  14. Bruce Samuelson"!
  15.  
  16. 'From VisualWorks(TM), Release 1.0 of 8 October 1992 on 8 July 1993 at 3:12:18 pm'!
  17.  
  18. !Set methodsFor: 'public domain'!
  19.  
  20. hashStatistics
  21.     "Copyright (c) 1993 by Bruce Samuelson. Released to the public domain.
  22.  
  23.     This method tests how well the receiver is hashed. It works for Set and
  24.     its subclasses such as IdentitySet, Dictionary, and IdentityDictionary. It is
  25.     compatible with ParcPlace ObjectWorks 4.1 and VisualWorks 1.0. but
  26.     not ObjectWorks 4.0 because OW 4.1 changed the way hash probes are
  27.     calculated. It relies on intimate details of the findElementOrNil: and
  28.     findKeyOrNil: methods and may fail to work with ParcPlace's next release.
  29.  
  30.     Return an array:
  31.  
  32.     at: 1    basicSize of dictionary 
  33.     at: 2    size of dictionary
  34.     at: 3    average miss of hash function
  35.             N means it took N steps to find a hole for the average element
  36.             0 means hash is ideal; large number means hash is bad 
  37.     at: 4    histogram of misses
  38.  
  39.     Please forgive the usage of isKindOf:. I'm trying to limit this public domain
  40.     fileout to two methods, Set>>hashStatistics and Bag>>sortedElements.
  41.     If I didn't use the kludge, I'd either have to include several versions of
  42.     hashStatistics or several support methods in scattered classes.
  43.  
  44.     The first test below measures how well the Smalltalk dictionary is hashed.
  45.     In the original VW 1.0 image, its average miss is 7 steps, which is atrocious.
  46.     The worst element misses by 195 steps!! In my image, which has a few
  47.     hundred classes added, the average miss is about 1, presumably because
  48.     it got rehashed to a better layout as it grew. The second and third tests show
  49.     measurements on sets derived from the Smalltalk dictionary. The reason why
  50.     the first three tests yield different results is left as an exercise for the reader."
  51.  
  52.     "Smalltalk hashStatistics"
  53.     "Smalltalk keys hashStatistics"
  54.     "(Smalltalk keys collect: [:key | key asString]) hashStatistics"
  55.     "Set new hashStatistics"
  56.     "(Set with: 1.1 with: 2.2 with: 3.3) hashStatistics"
  57.     "(IdentitySet with: #size with: #+ with: #do:) hashStatistics"
  58.     "(Dictionary with: 'How'->'adv' with: 'are'->'v' with: 'you?'->'n') hashStatistics"
  59.     "(IdentityDictionary with: 1->1 with: 2->4 with: 3->9) hashStatistics"
  60.  
  61.     | enumerate hash access compare basicSize size totalMiss histogram |
  62.     (self isKindOf: Dictionary)        "Embarassing: see apology above."
  63.         ifTrue:
  64.             [enumerate := #keysDo:.
  65.             access := (self isKindOf: IdentityDictionary) ifTrue: [#yourself] ifFalse: [#key]]
  66.         ifFalse:
  67.             [enumerate := #do:.
  68.             access := #yourself].
  69.      ((self isKindOf: IdentityDictionary) or: [self isKindOf: IdentitySet])        "Red faced: see apology above."
  70.         ifTrue:
  71.             [hash := #identityHash.
  72.             compare := #==]
  73.         ifFalse:
  74.             [hash := #hash.
  75.             compare := #=].
  76.     basicSize := self basicSize.
  77.     size := self size.
  78.     totalMiss := 0.
  79.     histogram := Bag new: 100.
  80.     self perform: enumerate with:
  81.         [:elementOrKey |
  82.         | miss index probe |
  83.         miss := 0.
  84.         index := self initialIndexFor: (elementOrKey perform: hash) boundedBy: basicSize.
  85.         [(probe := self basicAt: index) notNil and: [(probe perform: access) perform: compare with: elementOrKey]]
  86.             whileFalse: 
  87.                 [miss := miss + 1.
  88.                 (index := index + 1) > basicSize ifTrue: [index := 1]].
  89.         histogram add: miss.
  90.         totalMiss := totalMiss + miss].
  91.     ^Array
  92.         with: basicSize
  93.         with: size
  94.         with: (totalMiss / (size max: 1)) asFloat
  95.         with: histogram sortedElements! !
  96.  
  97.  
  98. !Bag methodsFor: 'public domain'!
  99.  
  100. sortedElements
  101.     "Copyright (c) 1993 by Bruce Samuelson. Released to the public domain.
  102.  
  103.     Answer a collection of elements with counts, sorted by element. A version with 
  104.     unoptimized implementation used to be in PPS ObjectWorks 4.0."
  105.  
  106.     | tmp |
  107.     tmp := OrderedCollection new: contents basicSize.
  108.     contents associationsDo: [:assn | tmp add: assn].
  109.     ^tmp asSortedCollection "faster than adding elements individually to sorted coll"! !
  110.